package sort;


import java.util.concurrent.ThreadLocalRandom;

public class Sort {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();
    /**
     * 原地堆排序，将最大堆的堆顶元素与数组最后一个元素进行交换
     * 数组长度-1后继续堆化
     * 注意向下调整从从后往前第一个非叶子节点开始，
     * 节点下标为：(arr.length - 1 - 1) / 2
     */
    public void heapSort(int[] arr){
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            //开始进行元素向后交换
            swap(arr,0,i);
            //交换后堆顶元素下沉，继续堆化
            siftDown(arr,0,i);
        }
    }
    /**
     * 向下调整
     * @param n 数组中需要堆化的元素个数
     */
    private void siftDown(int[] arr, int i, int n) {
        while ((2 * i) + 1 < n) {
            int j = 2 * i + 1;
            if(j + 1 < n && arr[j + 1] > arr[j]){
                j = j + 1;
            }
            if(arr[i] >= arr[j]){
                break;
            }else {
                swap(arr,i,j);
                i = j;
            }
        }
    }

    /**
     * 冒泡排序
     */
    public void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            boolean step = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if(arr[j] > arr[j + 1]){
                    step = true;
                    swap(arr,j,j + 1);
                }
            }
            if(!step){
                break;
            }
        }
    }
    private void swap(int[] arr, int j, int i) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 直接选择排序
     * @param arr
     */
    public void selectionSort(int[] arr){
        //每次从待排序数组中选择最小值放在待排序数组的最前面
        for (int i = 0; i < arr.length - 1; i++) {
            //min变量存储了最小值元素的下标
            int min = i;
            //每次从无序区间中选择最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            swap(arr,i,min);
        }
    }

    /**
     * 双向选择排序，每次选出最小值放前面，最大值放后面
     * @param arr
     */
    public void selectionSortOP(int[] arr){
        int low = 0;
        int high = arr.length - 1;
        //有序区间变成从[0,low+1)
        while (low < high){
            int min = low;
            int max = low;
            for (int i = low + 1; i < high; i++) {
                if (arr[i] > arr[max]){
                    max = i;
                }
                if (arr[i] < arr[min]){
                    min = i;
                }
            }
            //min存储了无需区间最小值，max存储无需区间最大值
            swap(arr,low,min);
            if (max == low){
                max = min;
            }
            swap(arr,max,high);
            low += 1;
            high -= 1;
        }
    }

    /**
     * 直接插入排序
     * 每次选择无需区间第一个元素，插入到有序区间的合适位置
     * @param arr
     */
    public void insertionSortBase(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]){
                    swap(arr,j,j - 1);
                }else {
                    break;
                }
            }
        }
    }

    /**
     * 由于插入是在有序区间的插入，因此可以使用二分查找的办法来快速定位插入的位置
     * @param
     */
    public void insertionSortBS(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            int low = 0;
            int high = i;
            while (low < high){
                int mid = (low + high) / 2;
                //将相等的值放在左半区间，保证稳定性
                //不选中那个相等的值，就不会被移动
                if (val >= arr[mid]){
                    low = mid + 1;
                }else {
                    high = mid;
                }
            }
            //数据搬移
            for (int j = i; j > low; j--) {
                arr[j] = arr[j - 1];
            }
            arr[low] = val;
        }
    }

    /**
     * 希尔排序
     * 先选定一个gap，将待排序的数据中所有记录按gap分组，所有距离为gap的数据放在同一组，将组内元素排序。
     * 然后不断缩小gap的大小直到变为1，当gap变为1时，整个数组近乎有序。调用普通插入排序统一排序即可
     * （普通插入排序在近乎有序的数组中排序效率是非常高的）
     * @param
     */
    public void shellSort(int[] arr){
        int gap = arr.length >> 1;
        while (gap > 1){
            //不断按照gap分组，组内插入排序
            insertionSortGap(arr,gap);
            gap /= 2;
        }
        //整个数组的插入排序
        insertionSortGap(arr,1);
    }

    private void insertionSortGap(int[] arr, int gap) {
        //最外层从gap开始，不断走到数组末尾，
        //子数组分别交替进行，不是每个组每个组的比较
        for (int i = gap; i < arr.length; i++) {
            //比较
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j = j - gap) {
                    swap(arr,j,j - gap);
            }
        }
    }
    private  void insertBase(int[] arr,int l,int r) {
        // 有序区间[l..i)
        // 无序区间[i,r]
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j-1);
            }
        }
    }
    /**
     * 归并排序
     * @param arr
     */
    public void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 在数组的[l...r]上进行归并排序
     * @param arr
     * @param l
     * @param r
     */
    public void mergeSortInternal(int[] arr, int l, int r) {
//        if (r - l<= 15) {
//            // 拆分后的小区间直接使用插入排序，不再递归
//            insertBase(arr,l,r);
//            return;
//        }
        if(l >= r){
            //区间只剩下一个元素
            return;
        }
        //预防栈溢出
        int mid = l + ((r - l) >> 1);
        //再拆分后的两个小数组上进行归并排序
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);

        if (arr[mid] > arr[mid + 1]) {
            merge(arr,l,mid,r);
        }
    }
    /**
     * 归并排序非递归，自底向上写法
     * @param arr
     */
    private void mergeSortNonRecursion(int[] arr){
        //sz表示每次合并的元素个数，sz区间不断成倍扩大
        for (int sz = 1; sz <= arr.length; sz = sz + sz) {
            //merge过程，i表示每次merge开始索引下标
            for (int i = 0; i + sz < arr.length; i += sz + sz) {
                merge(arr,i,i + sz - 1,Math.min(i + 2 * sz - 1,arr.length - 1));
            }
        }
    }
    /**
     * 将已经有序的两个区间合并为一个大的有序区间
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private void merge(int[] arr, int l, int mid, int r) {
        //开辟一个大小和合并后数组大小相同的数组
        int[] temp = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            //temp的索引是从0开始的，而arr拷贝过来的只是原数组的一小部分区间
            //有l个单位的偏移量
            temp[i - l] = arr[i];
        }
        //遍历temp，更改arr的部分区间
        //i对应左半区间索引
        int i = l;
        //j对应右半区间起始索引
        int j = mid + 1;
        //k表示处理到的下标索引
        for (int k = l; k <= r; k++) {
            if(i > mid){
                //左半区间元素放完了
                arr[k] = temp[j - l];
                j ++;
            }else if (j > r){
                arr[k] = temp[i - l];
                i ++;
            }else if (temp[i - l] <= temp[j - l]){
                arr[k] = temp[i - l];
                i ++;
            }else {
                arr[k] = temp[j - l];
                j ++;
            }
        }
    }
//    /**
//     * 快速排序
//     * @param
//     */
//    public void quickSort(int[] arr){
//        quickSortInternal(arr,
//                0,
//                arr.length - 1);
//    }
//
//    private void quickSortInternal(int[] arr,
//                                   int lowIndex,
//                                   int highIndex) {
//        //由于是闭区间，所以区间个数+1
//        int size = highIndex - lowIndex + 1;
//        if (size <= 1){
//            return;
//        }
//        //选择其中一个数出来 -> arr[lowIndex]
//        //执行patition，小的放左，大的放右
//        //keyIndex是经过patition之后最终选出的下标
//        int keyIndex = patition(arr,lowIndex,highIndex);
//        //对keyIndex的左边和右边再进行patition
//        quickSortInternal(arr,lowIndex,keyIndex - 1);
//        quickSortInternal(arr,keyIndex + 1,highIndex);
//    }
//    /**
//     * 1.选择arr[lowIndex]在 的数
//     * 2.需要遍历整个区间，和选出来的数作比较
//     * 3.保证<=的在左边,>=的在右边
//     */
//    private int patition(int[] arr, int lowIndex, int highIndex) {
//        return patitionS2F(arr,lowIndex,highIndex);
//    }
//
//    private int patitionHover(int[] arr, int lowIndex, int highIndex) {
//        int leftIndex = lowIndex;
//        int rightIndex = highIndex;
//        //选择最左边的数
//        int key = arr[lowIndex];
//        //选择了最左边，从右边先走
//
//        //停止条件 leftIndex == rightIndex
//        //循环的继续条件 leftIndex < rightIndex
//        while (leftIndex < rightIndex){
//            while (leftIndex < rightIndex && arr[rightIndex] >= key){
//                rightIndex --;
//            }
//            //走到这里说明[rightIndex]遇到小的值了
//            while (leftIndex < rightIndex && arr[leftIndex] <= key){
//                leftIndex ++;
//            }
//            swap(arr,leftIndex,rightIndex);
//        }
//        swap(arr,lowIndex,leftIndex);
//
//        return leftIndex;
//    }
//
//    private int patitionPotholing(int[] arr, int lowIndex, int highIndex){
//        int leftIndex = lowIndex;
//        int rightIndex = highIndex;
//        //选择最左边的数
//        int key = arr[lowIndex];
//        //选择了最左边，从右边先走
//        while (leftIndex < rightIndex){
//            while (leftIndex < rightIndex && arr[rightIndex] >= key){
//                rightIndex --;
//            }
//
//            arr[leftIndex] = arr[rightIndex];
//            //走到这里说明[rightIndex]遇到小的值了
//            while (leftIndex < rightIndex && arr[leftIndex] <= key){
//                leftIndex ++;
//            }
//            arr[rightIndex] = arr[leftIndex];
//        }
//
//        arr[leftIndex] = key;
//        return leftIndex;
//    }
//    private int patitionS2F(int[] arr, int lowIndex, int highIndex){
//        int separateIndex = lowIndex + 1;
//        for (int i = lowIndex + 1; i <= highIndex; i++) {
//            if(arr[i] < arr[lowIndex]){
//                swap(arr,i,separateIndex);
//                separateIndex ++;
//            }
//        }
//        swap(arr,lowIndex,separateIndex - 1);
//        return separateIndex;
//    }

//    /**
//     * 归并排序
//     * @param
//     */
//    public void mergeSort(int[] arr){
//        mergeSortInternal(arr, 0, arr.length);
//    }
//    //区间范围是左闭右开的
//    private void mergeSortInternal(int[] arr, int lowIndex, int highIndex) {
//        int size = highIndex - lowIndex;
//        if(size <= 1){
//            return;
//        }
//
//        int middleIndex = (lowIndex + highIndex) / 2;
//        //区间被分成左右两份[leftIndex,middleIndex] , [middleIndex,rightIndex]
//        mergeSortInternal(arr,lowIndex,middleIndex);
//        mergeSortInternal(arr,middleIndex,highIndex);
//
//        //左右两个区间都有序
//        marge(arr,lowIndex,middleIndex,highIndex);
//    }
//
//    private void marge(int[] arr, int lowIndex, int middleIndex, int highIndex) {
//        int size = highIndex - lowIndex;
//        int[] extraArray = new int[size];
//
//        int leftIndex = lowIndex;
//        int rightIndex = middleIndex;
//        int extraIndex = 0;
//
//        //两个队伍都有元素
//        while (leftIndex < middleIndex && rightIndex < highIndex){
//            if (arr[leftIndex] <= arr[rightIndex]){
//                extraArray[extraIndex] = arr[leftIndex];
//                leftIndex ++;
//            }else {
//                extraArray[extraIndex] = arr[rightIndex];
//                rightIndex ++;
//            }
//            extraIndex ++;
//        }
//
//        //有一对元素空
//        if(leftIndex < middleIndex){
//            while (leftIndex < middleIndex){
//                extraArray[extraIndex++] = arr[leftIndex++];
//            }
//        }else {
//            while (rightIndex < highIndex){
//                extraArray[extraIndex++] = arr[rightIndex++];
//            }
//        }
//
//        //最后，把数据从新数组统一搬回去
//        for (int i = 0; i < size; i++) {
//            arr[i + lowIndex] = extraArray[i];
//        }
//    }
    public void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length - 1);
    }

    private void quickSortInternal(int[] arr, int l, int r) {
        if (r - l<= 15) {
            // 拆分后的小区间直接使用插入排序，不再递归
            insertBase(arr,l,r);
            return;
        }
        //选择一个基准值，返回他的下标
        int p = partition(arr,l,r);
        //在小于基准值的区间进行快速排序
        quickSortInternal(arr,l,p - 1);
        //在大于基准值的区间上进行快速排序
        quickSortInternal(arr,p + 1,r);
    }
    /**
     * 在arr[l...r]
     * @return
     */
    private int partition(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
        int j = l;
        //arr[l + 1 ... j] < v
        //arr[j + 1 ... i) >= v
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v){
                swap(arr,j + 1,i);
                //小于v的元素值新增一个
                j ++;
            }
        }
        //此时j下标对应的就是最后一个小于v的元素。交换j和v的值，就把基准值放到了最终位置
        swap(arr,l,j);
        return j;
    }


    public static void main(String[] args) throws Exception {
        int[] arr = {3,5,2,1,7,6,9,8,4};
        Sort sort = new Sort();
        sort.quickSort(arr);
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < arr.length;i++){
            sb.append(arr[i]);
            if(i != arr.length - 1){
                sb.append(",");
            }
        }
        sb.append("]");
        System.out.println(sb);
//        int n = 50000;
//        int[] arr = SortHelper.generateRandomArray(n,0,Integer.MAX_VALUE);
//        int[] arrCopy = SortHelper.arrCopy(arr);
//        SortHelper.testSort("selectionSort",arr);
//        SortHelper.testSort("selectionSortOP",arrCopy);
    }
}

